#include<iostream>
#include<vector>
using namespace std;
//哈希表的开散列实现
//关于负载因子的确定：最好的情况就是刚好每个位置都有一个节点,当再次插入的时候就会发生哈希冲突,所以当负载因子为1的时候就扩容
//此时哈希表当中每个元素都是一个桶，桶里面放的是一条单链表,哈希表的元素是单链表的头结点
//此时不需要存储每个位置的状态，因为哈希地址相同的元素放在了同一个桶当中==>放在同一条链表当中，不会影响和自己哈希地址不相同的元素
//使用除留余数法时，必须保证左右两侧都是整形，即必须要求key为整形，但是如果哈希表当中存储的元素不是整形，那么就没办法使用
//解决办法:增设一个模板参数，用于将key转化为整形，凡是不是整形的元素类型都必须提供一个仿函数用于将key转为整形
//提供一个默认的仿函数，用于直接将key转为整形返回

template<class K>
struct Hash
{
  //将返回类型设置为无符号类型，这样的话负数也可以处理
  //插入的时候不可以取绝对值插入,例如:-9和9  这样的话会因为冗余而不插入
  size_t operator()(const K& key) 
  {
    return key;
  }
};

//哈希表节点->本质是单链表节点
template<class K,class V>
struct HashNode
{
  pair<K,V> _kv;
  HashNode<K,V>* next;
  HashNode() //默认构造函数
    :next(nullptr)
  {}
  ~HashNode()
  {
    delete next;
    next = nullptr;
  }
  HashNode(const pair<K,V>& kv) :_kv(kv),next(nullptr)
  {}
};
template<class K,class V,class HashFunc = Hash<K>>
class HashTable
{
public:
  typedef HashNode<K,V> Node;
  HashTable() :n(0)
  {}
  bool insert(const pair<K,V>& kv)
  {
    //不允许数据冗余
    if(find(kv.first) != nullptr)
    {
      return false;
    }
    //判断是否需要扩容 -> 最初哈希表的大小为0,n也为0 || 负载因子为1  ==>可以简写为一个条件
    if(n == tables.size())
    {
      //此时不需要重新创建一个哈希结构,只需要创建一个哈希表
      //若创建一个哈希结构然后插入，会导致再开辟节点，浪费资源，不如直接使用已经有的节点
      vector<Node*> newTables;
      size_t newCapacity = tables.size() == 0 ? 10:tables.size()*2;
      newTables.resize(newCapacity);//不能使用reserve

      //遍历原哈希表
      for(int i = 0;i<tables.size();i++)
      {
        //每个位置都是一个桶,桶里面放的是单链表,tables[i]:单链表的头节点
        Node* cur = tables[i]; 
        //遍历这一条单链表,把节点重新节点哈希地址插入到新哈希表当中
        while(cur)
        {
          Node* next = cur->next;
          size_t start = HashFunc()(cur->_kv.first) % newTables.size(); //重新计算哈希地址
          //头插到对应的位置
          cur->next = newTables[start];
          newTables[start] = cur;
          cur = next;
        }
        //最后记得把原来哈希表的元素位置置为空，防止野指针
        tables[i] = nullptr;
      }
      tables.swap(newTables);
    }
    size_t start = HashFunc()(kv.first) % tables.size();
    Node* newnode = new Node(kv);
    newnode->next = tables[start];
    tables[start] = newnode;
    n++;
    return true;
  }
  Node* find(const K& key)
  {
    if(tables.size() == 0)
    {
      return nullptr;
    }
    //因为相同哈希地址的元素是放在 同一个桶==>放在同一条单链表当中的，所以只需要遍历这条单链表寻找即可
    size_t start = HashFunc()(key) % tables.size(); //记得%tables.size()!!!!!!!!!
    Node* cur = tables[start];
    while(cur != nullptr)
    {
      if(cur->_kv.first == key)
        return cur;
      cur = cur->next;
    }
    return nullptr;
  }
  bool erase(const K& key)
  {
    //不需要先查找该元素是否存在，因为如果存在的话还是要找到该元素的位置删除,相当于遍历了两遍，效率太低了
    if(tables.size() == 0)
    {
      return false;
    }
    size_t start = HashFunc()(key) % tables.size();
    Node* cur = tables[start];
    Node* prev = nullptr;//用于链接要删除节点的前后节点的关系
    while(cur)
    {
      if(cur->_kv.first == key)
      {
        //判断删除的是否是头节点
        if(prev == nullptr)
        {
          tables[start] = cur->next;
        }
        else  
        {
            prev->next = cur->next;
        }
        n--;
        delete cur;
        return true;
      }
      else 
      {
        prev = cur;
        cur = cur->next;
      }
    }
    //走到空也没有找到要删除的节点,说明该元素不存在
    return false;
  }
  //for test 
  void Print()
  {
    cout << "哈希表有效元素个数:" << n << endl;
    for(int i  = 0;i<tables.size();i++)
    {
      Node* cur = tables[i];
      cout <<"当前为第 "<< i <<"个桶:" << " ";
      while(cur)
      {
         cout << cur->_kv.first << " ";
         cur = cur->next;
      }
      cout << endl;
    }
  }
private:
  vector<Node*> tables;
  size_t n = 0;//给缺省值
};
int main()
{
  vector<int> v{3,23,33,43,20,30}; 
  HashTable<int,int> ht;
  // ht.insert({3,1});
  // ht.insert({23,1});
  // ht.insert({33,1});
  // ht.insert({43,1});
  // ht.insert({20,1});
  // ht.insert({30,1});
  for(auto& n:v)
    ht.insert({n,n});
  ht.Print();
  ht.erase(3);
  ht.erase(23);
  ht.insert({53,53});
  cout << ht.find(3) << endl;
  cout << ht.find(23) << endl;
  ht.Print();
  return 0;
}
